package redis;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author wen
 * @Date 2021/6/5
 *
 *  Redis可使用最大内存使用完了，是可以使用LRU算法进行内存淘汰的，那么什么是LRU算法呢？
 *
 * LRU(Least Recently Used)，即最近最少使用，是一种缓存置换算法。
 * 在使用内存作为缓存的时候，缓存的大小一般是固定的。当缓存被占满，这个时候继续往缓存里面添加数据，
 * 就需要淘汰一部分老的数据，释放内存空间用来存储新的数据。这个时候就可以使用LRU算法了。
 * 其核心思想是：如果一个数据在最近一段时间没有被用到，那么将来被使用到的可能性也很小，所以就可以被淘汰掉。
 *  参考： https://zhuanlan.zhihu.com/p/84507504
 *
 *   简单的LRU算法
 **/
public class LRUCache<k, v> {


    // 容量
    private int capacity;
    // 当前有多少节点统计
    private int count;

    //缓存节点
    private Map<k,Node<k, v>> nodeMap;

    private Node<k, v> head;
    private Node<k, v> tail;

    public LRUCache(int capacity){
        if(capacity < 1){
            throw new IllegalArgumentException(String.valueOf(capacity));
        }
        /**
         * his.capacity = capacity;
         *         this.nodeMap = new HashMap<>();
         *         //初始化头节点和尾节点，利用哨兵模式减少判断头结点和尾节点为空的代码
         *         Node headNode = new Node(null, null);
         *         Node tailNode = new Node(null, null);
         *         headNode.next = tailNode;
         *         tailNode.pre = headNode;
         *         this.head = headNode;
         *         this.tail = tailNode;
         */

        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        //初始化头节点和尾节点，利用哨兵模式减少判断头结点和尾节点为空的代码
        head = new Node<>(null,null);
        tail = new Node<>(null,null);
        head.next = tail;
        tail.pre = head;

    }

    // 增加元素
    public void put(k key, v value){
        Node<k, v> kvNode = nodeMap.get(key);
        if (kvNode == null){
            if (count >= capacity){
                //先移除一个节点
                removeNode();
            }
            Node<k, v> node = new Node(key, value);
            //添加节点
            addNode(node);
        }else {
            //移动节点到头节点
            moveToHead(kvNode);
        }

    }

    //获取元素
    public Node<k, v> get(k key){
        Node<k, v> node = nodeMap.get(key);
        if (node != null){
            moveToHead(node);
        }
        return node;
    }

    // 从map中删除,最后一个节点 并且删除链表中数据
    public void removeNode(){
        Node last = tail.pre;
        removeFromList(last);
        nodeMap.remove(last.key);
        count --;
    }

    //从链表里面移除
    public void removeFromList(Node<k, v> node){
        Node pre = node.pre;
        Node next = node.next;

        pre.next = next;
        next.pre = pre;

        node.next = null;
        node.pre = null;
    }

    // 除了链表要保存数据，map中也要保存
    public void addNode(Node<k, v> node){
        addToHead(node);
        nodeMap.put(node.key,node);
        count ++;
    }

    // 链表头部添加元素
    public void addToHead(Node<k, v> node){
        // 原先head的下一个节点元素
        Node next = head.next;

        // next 的线
        head.next = node;
        node.next = next;
        // pre的线路
        next.pre = node;
        node.pre = head;

    }

    public void moveToHead(Node<k, v> node){
        //先删除
        removeFromList(node);
        //再添加队列头
        addToHead(node);
    }

    class Node<k, v>{

        k key;
        v value;
        Node pre;
        Node next;

        public Node(k key, v value){
            this.key = key;
            this.value = value;
        }
    }
}
